#include<iostream>
#include<fstream>
#include<sstream>
#include <ctime>
#include <ratio>
#include <chrono>
#include<omp.h>
using namespace std;
const int col=3799,elinenum=1953,num_thread=8;
bool parallel=1; 
int tmp=0;
int bytenum=(col-1)/32+1;   
class bitmatrix{
public:
    int mycol;    
    int *mybyte;    
    bitmatrix(){ 
        mycol=-1;
        mybyte = new int[bytenum];
        for(int i=0;i<bytenum;i++)
            mybyte[i]=0; 
    }
    bool isnull(){  
        if(mycol==-1)return 1;
        return 0;
    }   
    void insert(int x){ 
        if(mycol==-1)mycol=x;
        int a=x/32,b=x%32;
        mybyte[a]|=(1<<b);
    }
    void doxor(bitmatrix b){
        for(int i=0;i<bytenum;i++)
            mybyte[i]^=b.mybyte[i];
        for(int i=bytenum-1;i>=0;i--)
            for(int j=31;j>=0;j--)
                if((mybyte[i]&(1<<j))!=0){
                    mycol=i*32+j;
                    return;
                }
        mycol=-1;  
    }
};
bitmatrix *eliminer=new bitmatrix[col],*eline=new bitmatrix[elinenum];
void readdata(){
    ifstream ifs;
    ifs.open("eliminer.txt");  
    string temp;
    while(getline(ifs,temp)){
        istringstream ss(temp);
        int x;
        int trow=0;
        while(ss>>x){
            if(!trow)trow=x;    
            eliminer[trow].insert(x);
        }
    }
    ifs.close();
    ifstream ifs2;
    ifs2.open("eline.txt");     
    int trow=0;
    while(getline(ifs2,temp)){
        istringstream ss(temp);
        int x;
        while(ss>>x){
            eline[trow].insert(x);
        }
        trow++;
    }
    ifs2.close();
}
void dowork(){  
    for(int i=0;i<elinenum;i++){
        while(!eline[i].isnull()){  
            int tcol = eline[i].mycol;  
            if(!eliminer[tcol].isnull())    
                eline[i].doxor(eliminer[tcol]);
            else{
                eliminer[tcol]=eline[i];    
                break;
            }
        }
    }
}
void dowork2(){
    int i,j;
    #pragma omp parallel if(parallel),num_threads(num_thread),private(i,j)
    for(i=col-1;i>=0;i--) 
        if(!eliminer[i].isnull()){
            #pragma omp for 
            for(j=0;j<elinenum;j++){
                if(eline[j].mycol==i)
                    eline[j].doxor(eliminer[i]);
            }
            }
        else{
            #pragma omp barrier
            #pragma omp single
            for(j=0;j<elinenum;j++){
                if(eline[j].mycol==i){
                    eliminer[i]=eline[j];
                    tmp=j+1;
                    break;
                    }
                tmp=j+2;
            }
            #pragma omp for
            for(j=tmp;j<elinenum;j++){
                if(eline[j].mycol==i)
                    eline[j].doxor(eliminer[i]);
            }
            }
}

void printres(){ 
    for(int i=0;i<elinenum;i++){
        if(eline[i].isnull()){puts("");continue;}   
        for(int j=bytenum-1;j>=0;j--){
            for(int k=31;k>=0;k--)
                if((eline[i].mybyte[j]&(1<<k))!=0){     
                    printf("%d ",j*32+k);
                }
                }
        puts("");
    }
}
int main(){
    readdata();
    using namespace std::chrono;
    high_resolution_clock::time_point t1 = high_resolution_clock::now();
    dowork2();
     high_resolution_clock::time_point t2 = high_resolution_clock::now();
    std::cout<<"serial: "<<duration_cast<duration<double>>(t2-t1).count()<<std::endl;
    system("pause");
    return 0;
}